package study.算法Algorithm.查找算法.二分查找;

//注意：使用二分查找的前提时：该数组是有序的
public class BinarySearch {

    public static void main(String[] args) {
        int arr[] = {1,8,10,89,1000,1234};
        int resIndex = m01(arr,0,arr.length,89);
        System.out.println("resIndex = " + resIndex);
    }

    /**
     *
     * @param arr  数组
     * @param left  左边的索引
     * @param right  右边的索引
     * @param findVal  要查找的值
     * @return  如果找到就返回下标，如果没有找到就返回-1
     */
    private static int m01(int[] arr, int left, int right, int findVal) {

        //当left>right时，说明递归整个数组后，没有找到
        if (left>right){
            return -1;
        }
        int mid = (left+right)/2;
        int midVal = arr[mid];
        if (findVal>midVal){  //向右递归查找
            return m01(arr,mid+1,right,findVal);
        }else if (findVal<midVal){  //向左边递归
            return m01(arr,left,mid-1,findVal);
        }else {
            return mid;
        }
    }
}
